Electronic Design Automation (EDA) concerns the correctness, reliability, productivity, and optimization of automated system construction. It is an interdisciplinary field, where electrical engineering and computer science intersect. In EDA, theoretical computer science (including algorithms, complexity, automata, logic, programming languages, etc.) finds rich and practical applications. On the other hand, some of the techniques developed in the EDA community have been much enhanced the state-of-the-art solvers on intractable problems. In this course we will study some representative problems and solutions making VLSI design an automatic process. In particular, we will cover system modeling, optimization, analysis, and verification.

The contents include

1. Introduction

Background history, VLSI design flow, etc.

2. Basics of Computation Theory and Mathematical Optimization


3. Models of computation

Finite state machines, automata, Petri-nets, etc.

4. High-level synthesis

Design space exploration, resource sharing, etc.

5. Logic synthesis

Data structures for Boolean function representation, two-level and multi-level logic optimization, technology mapping, timing analysis, etc.

6. Verification

Combinational and sequential equivalence checking, property checking, etc.

7. Physical design

Floorplanning, placement, routing, etc.

8. Testing

Combinational and sequential ATPG, design for testability, etc.

9. Advanced topics

Asynchronous circuit synthesis, neuromorphic systems, molecular computation, etc.